package com.practice.niuke.new_direct_practice.class09;

/**
 * 给出一组正整数arr， 你从第0个数向最后一个数， 每个数的值表示你从这个位置可以向右跳
 * 跃的最大长度。 计算如何以最少的跳跃次数跳到最后一个数。
 */
public class Code03_JumpGame {

	public static int jump(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int stemp = 0; // 现在跳了多少步了
		int cur = 0; // stemp步内，右边界：如果不增加步数，最远能到达的右边界。
		int next = 0;// stemp+1步内，右边界：如果再增加1步，最远能到达的右边界。
		for (int i = 0; i < arr.length; i++) {
			if (cur < i) {
				stemp++;
				cur = next;
			}
			next = Math.max(next, i + arr[i]);
		}
		return stemp;
	}

	public static void main(String[] args) {
		int[] arr = { 3, 2, 3, 1, 1, 4 };
		System.out.println(jump(arr));

	}

}
